Việc đào móng được khởi công vào tháng 3 năm 1993. Một nền móng khổng lồ đã được đào, độ sâu 21m đủ để nuốt trọn 5 tầng của tòa nhà. Suốt quá trình đào móng, mỗi đêm có khoảng 500 xe tải đất được bới lên. Để đặt được một tòa nhà chọc trời với trọng lượng của 300,000 tấn khối chắc chắn là một công trình kỹ thuật ấn tượng.

Một nền móng có thể chịu được hai tòa tháp như vậy đòi hỏi không chỉ sự hiểu biết sâu rộng về kỹ thuật mà còn là một lượng bê tông được đổ vào nhiều nhất trong lịch sử Malaysia – quốc gia mà hầu như mọi thứ đều được xây dựng bằng bê tông cốt thép.

Vì các tòa tháp càng lên cao càng phải vững, lớp phủ bằng thép không rỉ được trải lên mặt dựng, chứa khoảng 83,500 mét vuông miếng bọc thép không rỉ và 50,000 mét vuông kính nhiều lớp. Tháp Petronas chính là “một viên kim cương đa diện giữa ánh mặt trời”.

Một điểm nhấn không thể bỏ qua của tháp đôi Malaysia là cầu Skybridge, cấu trúc nối hai tòa tháp ở tầng 41 và 42. Đây là cấu trúc hai tầng cao nhất thế giới và một nhịp dài 58m. Một hệ thống bản lề và khớp mở phức tạp cùng với các bạc đạn hình cầu đảm bảo Skybridge đứng vững bất chấp hai tòa tháp có thể bị di chuyển hay vặn xoắn.

Cuối cùng là công đoạn xây đỉnh chóp của hai tòa tháp: các chóp chói lóa cao 73.5m bằng thép không rỉ, được thiết kế lại để mang đến cho tòa nhà độ cao 451.9m tính từ mặt đường. Các chóp, bao gồm một cột, một quả bóng ở ngọn, và một vòng cầu được nâng lên từng phần và ráp vào trong một tháng sau khi hai tòa tháp đã đạt đúng độ cao.

Petronas Twin Tower được hoàn thành năm 1998 với tổng chiều cao 452m và 88 tầng.